Masala #1034

Asadbek gullarni parvarishlashni yoqtiradi. U “Ci plus plusium” gullaridan o‘zining qator joylashgan $n$ ta tuvagining barchasiga ekdi. Birinchi kuni barcha gullarning bo‘yi 0 deb hisoblasa bo‘ladi. Shu kundan boshlab har kuni Asadbek:

• shunday $[l, r]$ oraliqni tanlaydiki, shu oraliqdagi barcha tuvaklardagi gullarning bo‘yi  bir xil bo‘lsin;
• $[l+1,r-1]$ oraliqdagi barcha tuvaklarga suv quyadi. Keyingi kungacha shu oraliqdagi tuvaklarda joylashgan gullar 1 birlikka ga o‘sadi.

Misol, $n=6$ uchun mos ravishda 1-2-3-kunlardagi gullarning bo‘yini quyidagicha tasvirlash mumkin:

1-kuni $[1,6]$ oraliq tanlangan va $[2,5]$ oraliqdagi tuvaklarga suv quyilgan.

2-kuni $[3,5]$ oraliq tanlangan va $[4,4]$ oraliqdagi tuvaklarga suv quyilgan.

0 yoki bir necha kundan so‘ng, Asadbek o‘zining gullari bilan maqtanmoqchi bo‘lib, har bir gulining bo‘yini $A$ massiviga yozib, uni sizga berdi ($A_i=i$-tuvakdagi gulning bo‘yi). Ammo ba’zi gullarining bo‘ylarini eslay olmagani uchun, ularning bo‘ylarini o‘rniga -1  sonini yozdi.

Sizning vazifangiz Asadbek bergan ma’lumotlarga ko‘ra, bugungi kunda uning gullari necha xil ko‘rinishda bo‘lishi mumkinligini sanashdir. Agarda Asadbek sizni aldagan bo‘lsa, 0 chiqaring.

Natija katta bo‘lishi mumkinligi sababli, natijani $10^9+7$ ga bo‘lingandagi qoldig‘ini chiqaring.

Kirish oqimining birinchi qatorida bitta butun son - $n(1 \le n \le 10^4)$ kiritiladi.

Keyingi qatorda $n$ ta butun son - Asadbek sizga bergan $A$ massiv elementlari kiritiladi. Massiv elementlari yoki -1 yoki $10^4$ dan oshmaydigan butun manfiy bo‘lmagan sonlardir.

Hozir Asadbekning gullari necha xil ko‘rinishda bo‘lishi mumkin ekanligini $10^9+7$ ga bo‘lgandagi qoldig‘ini chiqaring. U aldagan bo‘lsa 0 chiqaring.